package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         114,
		Discription: "二叉树转链表",
		Level:       2,
		Labels: map[string]int{
			"递归":      1,
			"二叉树":     1,
			"Moris遍历": 1,
		},
	})
}

// Flatten
// 找左子树最右边的节点（中序遍历的前一个），将该节点的Right指向当前根节点的右节点
// 把当前根节点的右节点换成左节点，把左节点置为nil
// 移动到根节点的右节点（也就是原来的左节点）
//
//	@param root
func Flatten(root *ds.TreeNode) {
	cur := root
	for cur != nil {
		right := cur.Right
		//找左子树的最右边的节点（左子树前序遍历最后一个遍历到的节点
		//如果左子树为nil就直接到右子树
		temp := cur.Left
		if temp != nil {
			for temp.Right != nil {
				temp = temp.Right
			}
			temp.Right = right
			cur.Right = cur.Left
			cur.Left = nil
		}

        cur=cur.Right
	}
}
